class BTreeNode:
    """
    BTreeNode represents a node in a B-tree.

    Attributes:
        keys: List of keys stored in the node.
        children: List of child nodes.
    """

    def __init__(self, keys=None, children=None):
        """
        Initialize a B-tree node with keys and children.

        Args:
            keys: List of keys to be stored in the node. Defaults to None.
            children: List of child nodes. Defaults to None.
        """
        self.keys = keys or []
        self.children = children or []

    def is_leaf(self):
        """
        Check if the node is a leaf node.

        Returns:
            True if the node is a leaf node, False otherwise.
        """
        return len(self.children) == 0

    def __repr__(self):
        """
        Returns a string representation of the BTreeNode.

        Returns:
            String representation of the BTreeNode.
        """
        return f"BTreeNode({self.keys})"


class BTree:
    """
    BTree represents a B-tree data structure.

    Attributes:
        root: Root node of the B-tree.
        order: Order of the B-tree.
    """

    def __init__(self, order):
        """
        Initialize an empty B-tree with the specified order.

        Args:
            order: Order of the B-tree.
        """
        self.root = BTreeNode()
        self.order = order

    def insert(self, key):
        """
        Insert a key into the B-tree.

        Args:
            key: Key to be inserted.
        """
        root = self.root
        if len(root.keys) == (2 * self.order) - 1:
            temp = BTreeNode()
            self.root = temp
            temp.children.append(root)
            self._split_child(temp, 0)
            self._insert_non_full(temp, key)
        else:
            self._insert_non_full(root, key)

    def _insert_non_full(self, node, key):
        """
        Helper method to insert a key into a non-full node of the B-tree.

        Args:
            node: Current node being visited.
            key: Key to be inserted.
        """
        i = len(node.keys) - 1
        if node.is_leaf():
            node.keys.append(None)
            while i >= 0 and key < node.keys[i]:
                node.keys[i + 1] = node.keys[i]
                i -= 1
            node.keys[i + 1] = key
        else:
            while i >= 0 and key < node.keys[i]:
                i -= 1
            i += 1
            if len(node.children[i].keys) == (2 * self.order) - 1:
                self._split_child(node, i)
                if key > node.keys[i]:
                    i += 1
            self._insert_non_full(node.children[i], key)

    def _split_child(self, node, index):
        """
        Helper method to split a child node of the B-tree.

        Args:
            node: Parent node.
            index: Index of the child node to be split.
        """
        order = self.order
        child = node.children[index]
        new_child = BTreeNode(keys=child.keys[order:], children=child.children[order:])
        node.keys.insert(index, child.keys[order - 1])
        node.children.insert(index + 1, new_child)
        child.keys = child.keys[:order - 1]
        child.children = child.children[:order]

    def search(self, key):
        """
        Search for a key in the B-tree.

        Args:
            key: Key to be searched.

        Returns:
            True if the key is found, False otherwise.
        """
        return self._search_helper(self.root, key)

    def _search_helper(self, node, key):
        """
        Helper method to search for a key in the B-tree.

        Args:
            node: Current node being visited.
            key: Key to be searched.

        Returns:
            True if the key is found, False otherwise.
        """
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1
        if i < len(node.keys) and key == node.keys[i]:
            return True
        elif node.is_leaf():
            return False
        else:
            return self._search_helper(node.children[i], key)

    def delete(self, key):
        """
        Delete a key from the B-tree.

        Args:
            key: Key to be deleted.
        """
        self._delete_helper(self.root, key)
        if len(self.root.keys) == 0 and len(self.root.children) == 1:
            self.root = self.root.children[0]

    def _delete_helper(self, node, key):
        """
        Helper method to delete a key from the B-tree.

        Args:
            node: Current node being visited.
            key: Key to be deleted.
        """
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1
        if i < len(node.keys) and key == node.keys[i]:
            if node.is_leaf():
                node.keys.pop(i)
            else:
                self._delete_internal_node(node, i)
        elif not node.is_leaf():
            self._delete_internal_node(node, i)

    def _delete_internal_node(self, node, index):
        """
        Helper method to delete a key from an internal node of the B-tree.

        Args:
            node: Current node being visited.
            index: Index of the key to be deleted.
        """
        key = node.keys[index]
        if len(node.children[index].keys) >= self.order:
            predecessor = self._get_predecessor(node, index)
            node.keys[index] = predecessor
            self._delete_helper(node.children[index], predecessor)
        elif len(node.children[index + 1].keys) >= self.order:
            successor = self._get_successor(node, index)
            node.keys[index] = successor
            self._delete_helper(node.children[index + 1], successor)
        else:
            self._merge_nodes(node, index)

    def _get_predecessor(self, node, index):
        """
        Helper method to get the predecessor key of a key in an internal node.

        Args:
            node: Current node being visited.
            index: Index of the key.

        Returns:
            Predecessor key.
        """
        node = node.children[index]
        while not node.is_leaf():
            node = node.children[-1]
        return node.keys[-1]

    def _get_successor(self, node, index):
        """
        Helper method to get the successor key of a key in an internal node.

        Args:
            node: Current node being visited.
            index: Index of the key.

        Returns:
            Successor key.
        """
        node = node.children[index + 1]
        while not node.is_leaf():
            node = node.children[0]
        return node.keys[0]

    def _merge_nodes(self, node, index):
        """
        Helper method to merge two child nodes of an internal node in the B-tree.

        Args:
            node: Parent node.
            index: Index of the first child node.
        """
        child1 = node.children[index]
        child2 = node.children[index + 1]
        child1.keys.append(node.keys[index])
        child1.keys.extend(child2.keys)
        child1.children.extend(child2.children)
        node.keys.pop(index)
        node.children.pop(index + 1)

    def display(self):
        """
        Display the B-tree.
        """
        self._display_helper(self.root, "")

    def _display_helper(self, node, indent):
        """
        Helper method to display the B-tree.

        Args:
            node: Current node being visited.
            indent: Indentation for the current level of the tree.
        """
        if node is not None:
            print(indent + str(node.keys))
            if not node.is_leaf():
                for child in node.children:
                    self._display_helper(child, indent + "\t")


if __name__ == "__main__":
    # Create a new B-tree with order 3
    b_tree = BTree(order=3)

    # Insert keys into the B-tree
    keys = [6, 4, 9, 1, 7, 12, 3, 5, 8, 10, 14, 2, 11, 13]
    for key in keys:
        b_tree.insert(key)

    # Display the B-tree
    print("B-tree structure:")
    b_tree.display()
    # Output:
    # B-tree structure:
    # [6]
    # 	[2, 4]
    # 	[8, 9]
    # 	[10, 11, 12]
    # 		[7]
    # 		[]
    # 		[]
    # 		[13, 14]

    # Search for a key in the B-tree
    search_key = 7
    is_found = b_tree.search(search_key)
    print(f"Key {search_key} is found: {is_found}")
    # Output:
    # Key 7 is found: True

    # Delete a key from the B-tree
    delete_key = 9
    b_tree.delete(delete_key)
    print(f"Deleted key {delete_key}")
    print("B-tree after deletion:")
    b_tree.display()
    # Output:
    # Deleted key 9
    # B-tree after deletion:
    # [6]
    # 	[2, 4]
    # 	[8, 10, 11, 12]
    # 		[7]
    # 		[]
    # 		[]
    # 		[13, 14]

